package 面试真题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/28
 * @description 共有件物品，每件物品价值为w[i]。你共有n次机会，每次可以拿一件物品，但如果你第次拿的物品价值超过（严格大于）m，
 * 则后续的第次[i+1,i+k]机会将作废，从第i+k+1次开始才可以继续拿物品。
 * 你每次可以拿任意一件物品，现在想知道在此规则下，你能拿到的物品总价值最大是多少？
 */
public class Demo04贝壳找房2022java秋招笔试题2第4题 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int k = Integer.parseInt(params[1]);
        int m = Integer.parseInt(params[2]);
        params = br.readLine().split(" ");
        int[] w = new int[n];
        long ltSum = 0;
        int ltCnt = 0;
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(params[i]);
            if (w[i] <= m) {
                ltSum += w[i];
                ltCnt++;
            }
        }
        Arrays.sort(w);
        long maxValue = 0;
        // base case为"不超过阈值的物品全拿"
        int index = -1, rest = n, lowbound = ltCnt;
        do {
            // 每次把价值小的剔除，争取多拿一次价值高于阈值的物品
            ltSum -= (index < 0 ? 0 : w[index]);
            long total = ltSum;
            rest = n - ltCnt;      // 剩余操作次数
            for (int i = 0; rest > 0 && n - 1 - i >= lowbound; i++) {
                // 用lowbound卡一下，避免累加到小于等于阈值的物品
                total += w[n - 1 - i];
                rest -= k + 1;
            }
            maxValue = Math.max(total, maxValue);
            index++;
        } while (--ltCnt >= 0);      // 少拿一个小于阈值的物品再试
        System.out.println(maxValue);
    }

}
